class NP-complete

Definition

Define language $L'$ as $\mathbf{NP}$-complete if $L'$ is NP-hard and $L' \in$ NP.

(see NP, NP-hard)

Notes

• if P≠NP, then by Ladner's theorem there exists problems which are $\mathbf{NP}$-intermediate (NPI), i.e. between NP and NPC in complexity
  • else (if P=NP), then P = NP = NPC
• intuition: if a problem X is in NPC, every problem Y in NP may be reduced to it, thus solving X efficiently means solving NP efficiently; similarly, every problem in NPC may be reduced to one in NP hard

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 42.
2. https://webdocs.cs.ualberta.ca/~zacharyf/courses/complexity_2019/notes/complexity-w19-lec04.pdf
3. https://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf
4. https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard